home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / emerald / emrldsys.lha / Language / Malloc / edenalloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-08-16  |  11.7 KB  |  354 lines
  1. #include <stdio.h>
  2. #if (EDENKERNEL || TRANSFER)
  3. #include "EdenKernel/h/stdTypes.h"
  4. #include "EdenKernel/h/kEvents.h"
  5. #endif (EDENKERNEL || TRANSFER)
  6.  
  7. /*  An implementation of malloc(3), free(3) using the QuickFit method.
  8.  *  Guy Almes, May 1983.
  9.  *
  10.  *  Cf. MALLOC(3) in the Unix manual for external specifications.
  11.  *
  12.  *  Cf. Chuck Weinstock's PhD thesis for a discussion of the techniques
  13.  *  used.  (Charles Weinstock, Dynamic Storage Allocation Techniques,
  14.  *  April 1976, CMU)
  15.  *  nb: Unlike the original QuickFit, this implementation assumes that
  16.  *  TailFit always works.  Also, we want to allow for some other user to
  17.  *  be using sbrk.
  18.  *
  19.  *  NOTE: change made on 11/29/84 by Mike Schwartz to call HoldSigs and
  20.  *  ReleaseSigs at beginning and end of malloc if signals weren't
  21.  *  already held (and running in Eden Kernel or EFT context).  This is needed
  22.  *  in case a Unix routine that uses malloc is called, so that signals
  23.  *  will be held as needed to protect the critical region variables during
  24.  *  the allocation.
  25.  *
  26.  *  Hacked by oystr.  While the external specification was met, the
  27.  *  internal behaviour of the standard malloc(3) was not.  To wit:
  28.  *  areas free'd do not have their contents touched until reallocated
  29.  *  (Almes actually fixed this after considerable pleading); it is
  30.  *  possible to do multiple free's of the same area - that is "x = malloc();
  31.  *  free(x); free(x);" causes no damage.  This turkey originally did
  32.  *  not detect such a situation even though the multiple free's caused
  33.  *  it to trash the list structures and blow up at some future malloc
  34.  *  call.  Realloc was also a disaster area, making the assumption that
  35.  *  the old block was in use, which is not necessarily the case.
  36.  */
  37. /*  The parts of Unix used by this module:
  38.  */
  39.  
  40. /*  From BRK(2):
  41.  */
  42.     extern char *brk();      /* set break to addr */
  43.     extern char *sbrk();     /* add incr to break */
  44.  
  45. /*  From END(3):
  46.  */
  47.     extern char end;                 /* first byte beyond bss region */
  48.  
  49. /*  Design parameters; these can be changed to tune the implementation
  50.  *  to a specific application.
  51.  */
  52.  
  53. #define GrainSize       8
  54. #define LogGrainSize    3
  55. #define HeaderSize      sizeof(int)
  56.     /* number of bytes: every allocated block is
  57.      * (k+1) * GrainSize, for k >= MinGrains
  58.      * GrainSize == (1 << LogGrainSize)
  59.      */
  60.  
  61. #define MinBytes        0
  62. #define MaxBytes        (SBrkChunk - HeaderSize)         /* = 1020 bytes */
  63. #define MinGrains       0
  64. #define MaxGrains       ((MaxBytes-MinBytes+1) >> LogGrainSize)
  65.     /* The implementation is tuned to use ExactFit for blocks in the range
  66.      * MinBytes .. MaxBytes
  67.      */
  68.  
  69. #define BtoG(b) ( ((b)-(GrainSize-HeaderSize) + GrainSize-1) >> LogGrainSize )
  70.     /* convert a number of bytes to a number of grains */
  71. #define GtoB(g) ( ((g) << LogGrainSize) + (GrainSize-HeaderSize) )
  72.     /* and vice versa */
  73.  
  74. #define Nil ((char *) 0)
  75.     /* a nil pointer; often coerced to various flavors of pointers */
  76.  
  77. #define SBrkChunk 1024
  78.     /* the number of bytes to get from sbrk when growing the Tail */
  79. #define roundUp(a,b) ((char *) ( ((int)(a) + (b)-1) & ~((b)-1) ))
  80.     /* round up an address to the nearest 1k boundary like sbrk does */
  81.  
  82. /* header for Big blocks allocated via MiscFit */
  83. typedef struct bigHeader {
  84.         struct bigHeader *bNext;  /* the next field links available blocks */
  85.         unsigned bSize;        /* the size of the block in bytes */
  86. } bHeader, *bHeaderPtr;
  87.  
  88. /* header for Small blocks allocated via ExactFit */
  89. typedef union smallHeader {
  90.         unsigned sSize;        /* the size of a used block in bytes */
  91.         union smallHeader *sNext;  /* the next field links available blocks */
  92. } sHeader, *sHeaderPtr;
  93.  
  94. static char *TailMin = &end;     /* points to 1st byte of Tail */
  95. static char *TailMax = &end;     /* points just beyond end of Tail */
  96.     /* invariants: TailMin and TailMax are each on int boundaries.
  97.      *      The area with addresses TailMin <= addr < TailMax is available.
  98.      *      &end <= TailMin <= TailMax == sbrk(0).
  99.      */
  100.  
  101. /*
  102.  * Free/in use magic numbers.  WARNING: if we ever get into 16MB+
  103.  * virtual addresses ( >24 bits), you will have to change the headers.
  104.  * The upper byte of the size field contains INUSEMAGIC if the
  105.  * block has been malloc'd but not freed, 0 if the block is free.
  106.  */
  107. #define INUSEMAGIC 0x55
  108. #define SETMAGIC   0x55000000
  109. #define CLRMAGIC   0x00FFFFFF
  110.  
  111. static char *TailFit(nBytes)
  112. register unsigned nBytes;
  113. {
  114.     register char *oldTailMin;
  115. #ifdef GORP
  116. fprintf(stderr,
  117.     "   TailFit(%d) called.  Tail: %x - %x.\n", nBytes, TailMin, TailMax);
  118. #endif
  119.     while (TailMax < TailMin+nBytes) {
  120.         register char *oldBreak = sbrk(SBrkChunk);
  121.         if ((int) oldBreak == -1) {
  122.             fprintf(stderr, "sbrk returned a -1!!");
  123.             return ( Nil );
  124.         }
  125.         if (oldBreak != TailMax) {  /* someone else did an sbrk! */
  126. #ifdef GORP
  127.             fprintf(stderr,
  128.                "TailFit: pushed TailMin from %x to %x.\n",
  129.                  TailMin, roundUp(oldBreak, sizeof(int)));
  130. #endif
  131.             TailMin = roundUp(oldBreak, sizeof(int));
  132.         }
  133.         TailMax = oldBreak + SBrkChunk;
  134.         if (TailMax != roundUp(TailMax, SBrkChunk)) {
  135.                                             /* bring TailMax to a page */
  136. #ifdef GORP
  137.             fprintf(stderr,
  138.                 "TailFit: rounding TailMax from %x to %x.\n",
  139.                 TailMax, roundUp(TailMax, SBrkChunk));
  140. #endif
  141.             TailMax = roundUp(TailMax, SBrkChunk);
  142.             (void) brk(TailMax);
  143.         }
  144.     } /* we now know we have enough in the Tail */
  145.     oldTailMin = TailMin;
  146.     TailMin += nBytes;
  147. #ifdef GORP
  148. fprintf(stderr,
  149.     "   TailFit returns %x.  Tail: %x - %x.\n", oldTailMin, TailMin, TailMax);
  150. #endif
  151.     return ( oldTailMin );
  152. } /* TailFit */
  153.  
  154. static bHeaderPtr BigList;
  155. /* BigLists points to a ring of zero or more available blocks, each marked
  156.  * with both a size and a next field.  This ring is used in the MiscFit
  157.  * portion of the algorithm, which is a simple FirstFit for very large blocks.
  158.  */
  159.  
  160. static char *MiscFit(nBytes)
  161. register unsigned nBytes;
  162. {
  163.     register bHeaderPtr CurrentHdr, PreviousHdr;
  164.     register unsigned oldSize;
  165.     register char *newBlock = Nil;
  166. #ifdef GORP
  167. fprintf(stderr, "   MiscFit(%d) called.\n", nBytes);
  168. #endif
  169.     if (BigList != (bHeaderPtr) Nil) {
  170.         PreviousHdr = BigList;
  171.         CurrentHdr = PreviousHdr->bNext;
  172.         oldSize = PreviousHdr->bSize;  /* save real size field, then ... */
  173.         PreviousHdr->bSize = nBytes;        /* ... forge a stopper value */
  174.         while (CurrentHdr->bSize < nBytes) {
  175.             PreviousHdr = CurrentHdr;
  176.             CurrentHdr = PreviousHdr->bNext;
  177.         } /* this loop always terminates due to the stopper value */
  178.         BigList->bSize = oldSize;    /* restore old size */
  179.         if (CurrentHdr->bSize >= nBytes) {   /* MiscFit worked */
  180.             PreviousHdr->bNext = CurrentHdr->bNext;
  181.             BigList =
  182.                 (PreviousHdr==CurrentHdr ? (bHeaderPtr) Nil : PreviousHdr);
  183.         CurrentHdr->bSize |= SETMAGIC;
  184.             newBlock = (char *) (CurrentHdr+1);
  185.         }
  186.     }
  187. #ifdef GORP
  188. fprintf(stderr, "   MiscFit returns %x.\n", newBlock);
  189. #endif
  190.     return( newBlock );
  191. } /* MiscFit */
  192.  
  193. /* p = malloc(nBytes);
  194.  * where nBytes is unsigned number of bytes needed and p is some pointer
  195.  */
  196.  
  197. static sHeaderPtr AvailList[MaxGrains-MinGrains+1];
  198. /* AvailList[MinGrains .. MaxGrains] is for ExactFit blocks
  199.  *
  200.  * AvailList[MinGrains..MaxGrains] each point to a LIFO singly-linked list of
  201.  * equal sized blocks.  These lists are used in the ExactFit portion of the
  202.  * algorithm.
  203.  */
  204.  
  205. char *malloc(reqBytes)
  206. unsigned reqBytes;
  207. {
  208.     register char *newBlock;
  209.     register unsigned nGrains = BtoG(reqBytes);
  210. #if (EDENKERNEL || TRANSFER)
  211.     extern int SigsHeld;
  212.     int SigsWereHeld;    
  213.  
  214.     SigsWereHeld = SigsHeld;
  215.     if (!SigsWereHeld) HoldSigs();  /* Make sure HoldSigs is called once (if 
  216.                            it wasn't already) if running in Eden
  217.                        Kernel context */
  218. #endif (EDENKERNEL || TRANSFER)
  219.  
  220. #ifdef GORP
  221. fprintf(stderr, "malloc(%d) called.\n", reqBytes);
  222. #endif
  223.  
  224.     if (reqBytes > MaxBytes) {
  225.         register unsigned nBytes = GtoB(nGrains);
  226.         newBlock = MiscFit(nBytes);
  227.         if (newBlock == Nil) {
  228.             bHeaderPtr newRawBlock = 
  229.                             (bHeaderPtr) TailFit(nBytes + sizeof(bHeader));
  230.             if (newRawBlock == (bHeaderPtr) Nil) {
  231.                 newBlock = Nil;
  232.             } else {
  233.                 newBlock = (char *) (newRawBlock+1);
  234.                 newRawBlock->bSize = nBytes | SETMAGIC;
  235.             }
  236.         }
  237.     } else {
  238.         register sHeaderPtr newRawBlock = AvailList[nGrains];
  239.         if (newRawBlock != (sHeaderPtr) Nil) {
  240.             AvailList[nGrains] = newRawBlock->sNext;
  241.             newRawBlock->sSize = GtoB(nGrains) | SETMAGIC;
  242.             newBlock = (char *) (newRawBlock + 1);
  243.         } else {
  244.             newRawBlock = (sHeaderPtr) TailFit(GtoB(nGrains)+sizeof(sHeader));
  245.             if (newRawBlock == (sHeaderPtr) Nil) {
  246.                 newBlock = Nil;
  247.             } else {
  248.                 newBlock = (char *) (newRawBlock + 1);
  249.                 newRawBlock->sSize = GtoB(nGrains) | SETMAGIC;
  250.             }
  251.         }
  252.     }
  253. #ifdef GORP
  254. fprintf(stderr, "malloc returns %x.\n", newBlock);
  255. fflush(stderr);
  256. #endif
  257.  
  258. #if (EDENKERNEL || TRANSFER)
  259.     if (!SigsWereHeld) ReleaseSigs();
  260. #endif (EDENKERNEL || TRANSFER)
  261.  
  262.     return( newBlock );
  263. } /* malloc */
  264.  
  265. free(ptr)
  266. char *ptr;
  267. {
  268.     register sHeaderPtr oldBlock = ((sHeaderPtr) ptr) - 1;
  269.     register unsigned nGrains = BtoG( (oldBlock->sSize & CLRMAGIC) );
  270.  
  271. #if (EDENKERNEL || TRANSFER)
  272.     extern int SigsHeld;
  273.     int SigsWereHeld;    
  274.  
  275.     SigsWereHeld = SigsHeld;
  276.     if (!SigsWereHeld) HoldSigs();  /* Make sure HoldSigs is called once (if 
  277.                            it wasn't already) if running in Eden
  278.                        Kernel context */
  279. #endif (EDENKERNEL || TRANSFER)
  280.     if ( ! (oldBlock->sSize & SETMAGIC) ) {
  281.     /* already free */
  282. #ifdef GORP
  283. fprintf(stderr, "free(%x) called returning %d grains (already free!).\n",
  284.     ptr, nGrains);
  285. #endif
  286.     return;
  287.     }
  288.     else oldBlock->sSize &= CLRMAGIC;
  289.  
  290. #ifdef GORP
  291. fprintf(stderr, "free(%x) called returning %d grains.\n", ptr, nGrains);
  292. #endif
  293.  
  294.     if (nGrains <= MaxGrains) {
  295.         oldBlock->sNext = AvailList[nGrains];
  296.         AvailList[nGrains] = oldBlock;
  297.     } else {
  298.         register bHeaderPtr oldBlock = ((bHeaderPtr) ptr) - 1;
  299.         if (BigList == (bHeaderPtr) Nil) {
  300.             BigList = oldBlock;
  301.             oldBlock->bNext = oldBlock;
  302.         } else {
  303.             oldBlock->bNext = BigList->bNext;
  304.             BigList->bNext = oldBlock;
  305.         }
  306.     }
  307.  
  308. #ifdef GORP
  309. fflush(stderr);
  310. #endif
  311. #if (EDENKERNEL || TRANSFER)
  312.     if (!SigsWereHeld) ReleaseSigs();
  313. #endif (EDENKERNEL || TRANSFER)
  314.  
  315. } /* free */
  316.  
  317. char *realloc(oldBlock, nBytes)
  318. register char *oldBlock;
  319. unsigned nBytes;
  320. {
  321.     register char *newBlock = malloc(nBytes);
  322.  
  323. #if (EDENKERNEL || TRANSFER)
  324.     extern int SigsHeld;
  325.     int SigsWereHeld;    
  326.  
  327.     SigsWereHeld = SigsHeld;
  328.     if (!SigsWereHeld) HoldSigs();  /* Make sure HoldSigs is called once (if 
  329.                            it wasn't already) if running in Eden
  330.                        Kernel context */
  331. #endif (EDENKERNEL || TRANSFER)
  332.  
  333.     if (newBlock != Nil) {
  334.         register int *newPtr = (int *) newBlock;
  335.         register int *oldPtr = (int *) oldBlock;
  336.         register sHeaderPtr oldRawBlock = ((sHeaderPtr) oldPtr) - 1;
  337.         register unsigned nGrains = ((oldRawBlock->sSize > nBytes)
  338.              ? BtoG(nBytes) 
  339.              : BtoG((oldRawBlock->sSize & CLRMAGIC)));
  340.         while (nGrains > 0) {
  341.             *newPtr++ = *oldPtr++;
  342.             *newPtr++ = *oldPtr++;
  343.             nGrains--;
  344.         }
  345.         *newPtr++ = *oldPtr++;
  346.         free(oldBlock);
  347.     }
  348.  
  349. #if (EDENKERNEL || TRANSFER)
  350.     if (!SigsWereHeld) ReleaseSigs();
  351. #endif (EDENKERNEL || TRANSFER)
  352.     return( newBlock );
  353. } /* realloc */
  354.